package weekone;

import java.util.HashMap;
import java.util.Map;

public class NumberOfSubarrays_1248 {
    public int numberOfSubarrays(int[] nums, int k) {
        int n = nums.length;
        int[] s = new int[n + 1]; // 0~n
        int[] count = new int[n + 1];
        // s[0] = 0;
        count[s[0]]++;
        //nums = [1,1,2,1,1], 取模
        //change to nums = [1,1,0,1,1]
        //有多少连续子数组（子段），子段和是k
        //暴力 双层循环 对于每个r, 考虑有几个l 使得s[r] - s[l-1]==k
        /**
         * for r = 1 ~ n
         *    for l = 1 ~ r [l,r]这个子段
         *        if s[r] - s[l-1]==k
         *        ans+=1
         * */
        for (int i = 1; i <= n; i++) {
            s[i] = s[i - 1] + nums[i - 1] % 2;
            count[s[i]]++;
        }

        int ans = 0;
        for (int i = 1; i <= n; i++) {
            // s[i] - s[j] = k, 求j的数量
            // s[j] = s[i] - k
            if (s[i] - k >= 0) {
                ans += count[s[i] - k];
            }
        }
        return ans;
    }

    public int numberOfSubarrays_1(int[] nums, int k) {
        int len = nums.length;
        int sum = 0;
        int count = 0;
        for (int i = 0; i < len; i++) {
            for (int j = i; j < len; j++) {
                sum+=nums[j];
                if (sum == k) {
                    count++;
                }
            }
            sum=0;
        }
        return count;
    }

    //前缀和+hashmap
    public int numberOfSubarrays_2(int[] nums, int k) {
        int len = nums.length;
        Map<Integer, Integer> map = new HashMap<>();
        int sum = 0;
        int count = 0;
        for (int i = 0; i < len; i++) {
            sum += nums[i];
            if(map.containsKey(sum - k)){
                count += map.get(sum - k);
            }
            map.put(sum, map.getOrDefault(sum, 0)+1);
        }

        return count;
    }
}
